Editing digital images, particularly digital photographs, is a common activity in both domestic and professional contexts. Common tasks include repairing (e.g., hiding tears, scratches, stains, and other damage), correcting (e.g., removing red eyes and other undesirable features in the image), and modifying (e.g., removing features of the image to change its semantics) a digital image.
In many such activities, the task may be accomplished by “filling” a region in the image with other image data. For example, in FIG. 1, a digital image 100 depicts a house with a satellite dish 102 on its roof. If a user wishes to remove the satellite dish 102 from the roof of the house in the image 100, the user may employ an existing approach called “cloning”. In cloning, the user manually copies one or more portions of backgrounds 104 and 106 and pastes them over the satellite dish 102 in appropriate locations and orientations, so as to hide the satellite dish 102. More sophisticated users may supplement this approach by manually introducing some local feathering at the borders of the pasted regions to conceal the seams.
However, the cloning approach is often time-consuming and tedious, if not impractical, and typically produces poor results at least in the following cases:                1. the region to fill (the “destination region”) is large, at least in one dimension (e.g., a whole person, a long scratch);        2. the area available in the rest of the image for potential background sources is small;        3. the regions to fill in are small but numerous (e.g., superimposed text); and        4. the region to fill in is surrounded by more than one type of texture, thereby requiring re-creation of inter-region boundaries.        
In addition, image regions often consist of both composite textures (i.e., multiple textures interacting spatially) and linear structures. Thus, image regions are typically complex products of mutual influences between different textures and structures, thereby limiting the effectiveness of cloning and pure texture synthesis.
Therefore, the existing approaches fail to satisfactorily fill destination regions in some images, are primarily manual, and are particularly ill-suited for many common scenarios.